package com.platform.modules.alg.alglib.p277;

import java.util.LinkedList;
import java.util.Queue;

public class P277 {
    private int maxn = 200005;
    private int maxe = 4000005;

    int Head[] = new int[maxn];
    int head[] = new int[maxn];
    int rear, tot;
    int tail[] = new int[maxn];
    int mark[] = new int[maxn];
    int sz[] = new int[maxn];
    int N, n, cnt, root, midedge, Max;
    node T[] = new node[2 * maxn];
    boolean vis[] = new boolean[maxn];
    public String output = "";

    // 原图
    private Edge edge[] = new Edge[maxe];
    // 重构图
    private Edge E[] = new Edge[maxe];

    public P277() {
        for (int i = 0; i < edge.length; i++) {
            edge[i] = new Edge();
            E[i] = new Edge();
        }
        for (int i = 0; i < T.length; i++) {
            T[i] = new node();
        }
    }

    // 原图初始化
    void init() {
        for (int i = 0; i < head.length; i++) {
            head[i] = -1;
        }
        tot = 0;
    }

    // 重构图初始化
    void INIT() {
        for (int i = 0; i < Head.length; i++) {
            Head[i] = -1;
        }
        rear = 0; // 下标从零开始
    }

    // 原图加边
    void add(int u, int v, int w) {
        edge[tot].v = v;
        edge[tot].w = w;
        edge[tot].nxt = head[u];
        head[u] = tot++;
    }

    // 重构图加边
    void ADD(int u, int v, int w) {
        E[rear].v = v;
        E[rear].w = w;
        E[rear].nxt = Head[u];
        Head[u] = rear++;
    }

    // 删除 u 结点的 i 号边
    void Delete(int u, int i) {
        if (Head[u] == i)
            Head[u] = E[i].nxt;
        else
            E[E[i].pre].nxt = E[i].nxt; // 跳过该边
        if (tail[u] == i) // 指向 u 结点的最后一条边，相当于尾指针
            tail[u] = E[i].pre;
        else
            E[E[i].nxt].pre = E[i].pre; // 双向链表修改前驱
    }

    // 保证每个点的度不超过 2
    void build(int u, int fa) {
        int father = 0;
        for (int i = head[u]; i != -1; i = edge[i].nxt) {
            int v = edge[i].v, w = edge[i].w;
            if (v == fa) continue;
            if (father == 0) // 还没有增加子节点，直接连上
            {
                ADD(u, v, w);
                ADD(v, u, w);
                father = u;
            } else // 已经有一个子节点，则创建一个新节点，把v连在新节点上
            {
                mark[++N] = 0;
                ADD(N, father, 0);
                ADD(father, N, 0);
                father = N;
                ADD(v, father, w);
                ADD(father, v, w);
            }
            build(v, u);
        }
    }

    // nxt 是下一条边的编号，pre 是上一条边的编号
    void get_pre() // 得到每条边的前驱
    {
        for (int i = 0; i < tail.length; i++) {
            tail[i] = -1;
        }
        for (int i = 1; i <= N; i++) {
            for (int j = Head[i]; j != -1; j = E[j].nxt) {
                E[j].pre = tail[i];
                tail[i] = j; // 指向 u 结点的最后一条边，相当于尾指针
            }
        }
    }

    // 重构图
    void rebuild() {
        // 重构图初始化
        INIT();
        N = n;
        for (int i = 1; i <= N; i++)
            mark[i] = 1;
        build(1, 0);
        get_pre(); // 得到每条边的前驱
        init(); // 原图初始化
    }

    void dfs1(int u)//测试重建树结果
    {
        vis[u] = true;
        for (int i = Head[u]; i != -1; i = E[i].nxt) {
            int v = E[i].v, w = E[i].w;
            if (vis[v]) continue;
            output += u + "\t" + v + "\t" + w + "\n";
            dfs1(v);
        }
    }

    // 求解每个子树大小
    void dfs_size(int u, int fa, int dis) {
        add(u, root, dis);//添加每个点到root的距离到距离树
        if (mark[u] == 1)//如果是白点，则压入根节点root的队列，dis为u到根root的距离
            T[root].q.add(new point(u, dis));//队列中保存白点及其到root的距离
        sz[u] = 1;
        for (int i = Head[u]; i != -1; i = E[i].nxt) {
            int v = E[i].v, w = E[i].w;
            if (v == fa) continue;
            dfs_size(v, u, dis + w);
            sz[u] += sz[v];
        }
    }

    void dfs_midedge(int u, int code)//找中心边
    {
        if (Math.max(sz[u], sz[T[root].rt] - sz[u]) < Max) {
            Max = Math.max(sz[u], sz[T[root].rt] - sz[u]);//sz[T[root].rt]为该子树结点总数
            midedge = code;
        }
        for (int i = Head[u]; i != -1; i = E[i].nxt) {
            int v = E[i].v;
            if (i != (code ^ 1))
                dfs_midedge(v, i);
        }
    }

    void PushUP(int id) // 更新 id 的ans
    {
        T[id].ans = -1; // 初始为-1
        while (!T[id].q.isEmpty() && mark[T[id].q.peek().u] == 0)//弹出黑点
            T[id].q.poll();
        int ls = T[id].ls, rs = T[id].rs; //ls为左儿子，rs为右儿子
        if (ls == 0 && rs == 0)//根没有左右儿子
        {
            if (mark[T[id].rt] == 1)//根为白结点
                T[id].ans = 0;
        } else {
            if (T[ls].ans > T[id].ans)//如果左儿子的结果大于根
                T[id].ans = T[ls].ans;
            if (T[rs].ans > T[id].ans)//如果右儿子的结果大于根
                T[id].ans = T[rs].ans;
            if (!T[ls].q.isEmpty() && !T[rs].q.isEmpty())//穿过中心边的
                T[id].ans = Math.max(T[id].ans, T[ls].q.peek().dis + T[rs].q.peek().dis + T[id].midlen);
        }
    }

    // id:树节点编号
    void DFS(int id, int u) {
        root = id;
        Max = N;
        midedge = -1;
        T[id].rt = u;
        dfs_size(u, 0, 0); // 求解每个子树大小
        dfs_midedge(u, -1);//找中心边
        if (midedge != -1) {
            //中心边的左右2点
            int p1 = E[midedge].v;//p1:v midedge: u->v
            int p2 = E[midedge ^ 1].v;//p2:u
            output += "中心边：\n";
            output += p2 + "——" + p1 + "\n";
            //中心边长度
            T[id].midlen = E[midedge].w;
            //左右子树
            T[id].ls = ++cnt;
            T[id].rs = ++cnt;
            //删除中心边
            Delete(p1, midedge ^ 1);//删除p1结点的i号边
            Delete(p2, midedge);
            DFS(T[id].ls, p1);
            DFS(T[id].rs, p2);
        }
        PushUP(id);//更新rt的ans
    }

    public String cal(String input) {
        String[] line = input.split("\n");
        n = Integer.parseInt(line[0]);
        init(); // 原树初始化
        int u, v, w;
        for (int i = 1; i < n; i++) {
            String[] num = line[i].split(" ");
            u = Integer.parseInt(num[0]);
            v = Integer.parseInt(num[1]);
            w = Integer.parseInt(num[2]);
            add(u, v, w);
            add(v, u, w);
        }
        rebuild(); // 重建树
        //memset(vis,false,sizeof(vis));
        dfs1(1);//测试重建树结果
        DFS(cnt = 1, 1); // 求解答案
        output += T[1].ans + "\n";
        output += T[2].ans + "\n";
        output += T[3].ans + "\n";
        return output;
    }
}

class Edge {
    int v, w, nxt, pre;
}

class point implements Comparable {
    int u, dis;

    point() {
    }

    point(int _u, int _dis) {
        u = _u;
        dis = _dis;
    }

    @Override
    public int compareTo(java.lang.Object o) {
        return this.dis < ((point) o).dis ? -1 : 1;
    }
}

class node {
    int rt; // 根节点编号
    int midlen; // 中心边的权值
    int ans; // 答案(最长树链)
    int ls, rs; // 左右子树编号
    Queue<point> q = new LinkedList<point>();
}
